package 剑指专题.动态规划;


/*
 * Author：江松
 * Date：2023/3/20 20:35
 *
 连续子数组和:
 定义：dp(i)为以第i个数结尾的序列，序列和的最大值
 划分：根据上一个状态的正负
 转移：max(a[i],dp[i-1]+a[i])


 */

public class Main1 {
    //因为只与前一个状态有关，可以进行优化
    public int FindGreatestSumOfSubArray(int[] array) {
        int dp=Integer.MIN_VALUE;
        int ans=Integer.MIN_VALUE;
        for(int i=0;i<array.length;++i){
            dp=Math.max(array[i],dp+array[i]);
            ans=Math.max(dp,ans);
        }
        return ans;
    }



    /*
    public int FindGreatestSumOfSubArray(int[] array) {
        int dp[]=new int[array.length+1];
        //
        int ans=Integer.MIN_VALUE;
        for(int i=1;i<=array.length;++i){
            if(dp[i-1]>0){
                dp[i]=dp[i-1]+array[i];
            }else{
                dp[i]=array[i-1];
            }
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }
    */
}
